package leetcode;
/**
 * 142.环形链表Ⅱ：返回入环时的节点
 * 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
 * 输入：head = [3,2,0,-4], pos = 1
 * 输出：返回索引为 1 的链表节点
 * 解释：链表中有一个环，其尾部连接到第二个节点。
 */
public class Num_142 {
    //三个指针，当fast和low相遇时，third开始走，当low和third相遇时即为所求
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode low = head;
        ListNode third = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            low = low.next;
            if(fast == low){
                while(low != third){
                    low = low.next;
                    third = third.next;
                }
                //当low == third时，即为所求节点
                return third;
            }
        }
        return null;
    }
}
